﻿#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cstdlib> // 包含malloc和free

using namespace std;

// 用于存储边的结构体，包含边的起点、终点和权重
struct Edge {
    int src, dest, weight;
};

// 比较函数，用于对边按照权重进行排序
bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// 查找并查集中元素i的根节点（父亲节点）
int find(int* parent, int i) {
    if (parent[i] == -1) // 如果i是根节点，返回i
        return i;
    return find(parent, parent[i]); // 递归查找根节点
}

// 合并两个元素所属的集合
void Union(int* parent, int x, int y) {
    int xset = find(parent, x); // 查找x的根节点
    int yset = find(parent, y); // 查找y的根节点

    if (xset != yset) { // 如果x和y不属于同一个集合，则合并
        parent[xset] = yset; // 将x的根节点设置为y的根节点
    }
}

// 普里姆算法（Prim's Algorithm）用于寻找加权无向图的最小生成树
vector<Edge> primMST(int V, int adjMatrix[][5]) {
    vector<Edge> result; // 用于存储最小生成树的边
    int* parent = new int[V]; // 动态分配内存，用于存储每个顶点的父节点
    for (int i = 0; i < V; ++i) {
        parent[i] = -1; // 初始化父节点数组，-1表示没有父节点
    }
    int key[5]; // 用于存储每个顶点到最小生成树的最小权重
    bool inMST[5]; // 标记顶点是否已经包含在最小生成树中
    for (int i = 0; i < V; ++i) {
        key[i] = INT_MAX; // 初始化所有顶点的最小权重为无穷大
        inMST[i] = false; // 初始化所有顶点都不在最小生成树中
    }

    key[0] = 0; // 从第一个顶点开始构建最小生成树

    for (int count = 0; count < V - 1; ++count) {
        int u = -1;
        int minWeight = INT_MAX; // 用于找到最小权重的顶点

        // 找到key中未包含在MST中且权值最小的顶点
        for (int v = 0; v < V; ++v) {
            if (!inMST[v] && key[v] < minWeight) {
                u = v;
                minWeight = key[v];
            }
        }

        inMST[u] = true; // 将顶点u添加到MST中

        // 更新与顶点u相邻的顶点的key值
        for (int v = 0; v < V; ++v) {
            if (adjMatrix[u][v] != INT_MAX && !inMST[v] && adjMatrix[u][v] < key[v]) {
                parent[v] = u; // 更新父节点
                key[v] = adjMatrix[u][v]; // 更新最小权重
            }
        }
    }

    // 构造MST的边
    for (int i = 1; i < V; ++i) {
        if (parent[i] != -1) {
            result.push_back({ parent[i], i, adjMatrix[i][parent[i]] }); // 添加边到结果中
        }
    }
    delete[] parent; // 释放内存
    return result;
}

// 克鲁斯卡尔算法（Kruskal's Algorithm）用于寻找加权无向图的最小生成树
vector<Edge> kruskalMST(int V, int adjMatrix[][5]) {
    vector<Edge> result; // 用于存储最小生成树的边
    vector<Edge> allEdges; // 用于存储图中所有的边
    for (int i = 0; i < V; ++i) {
        for (int j = i + 1; j < V; ++j) {
            if (adjMatrix[i][j] != INT_MAX) { // 如果两个顶点之间有边
                allEdges.push_back({ i, j, adjMatrix[i][j] }); // 添加边到allEdges中
            }
        }
    }

    // 按照边的权值对所有边进行排序
    sort(allEdges.begin(), allEdges.end(), compareEdges);

    // 并查集的初始化
    int* parent = new int[V]; // 动态分配内存，用于存储每个顶点的父节点
    for (int i = 0; i < V; ++i) {
        parent[i] = -1; // 初始化父节点数组，-1表示没有父节点
    }

    int edgeCount = 0; // MST中的边数

    for (Edge& edge : allEdges) {
        int x = find(parent, edge.src); // 查找边的起点的根节点
        int y = find(parent, edge.dest); // 查找边的终点的根节点

        // 如果将这条边添加到MST中不会形成环，则添加它
        if (x != y) {
            result.push_back(edge); // 添加边到结果中
            Union(parent, x, y); // 合并两个集合
            edgeCount++; // 增加MST中的边数

            // 当MST中有了V-1条边时，结束循环
            if (edgeCount == V - 1) {
                break;
            }
        }
    }
    delete[] parent; // 释放内存
    return result;
}

// 输出MST的边和它们的权值
void printMST(const vector<Edge>& mst) {
    cout << "Edge \tWeight" << endl;
    for (const Edge& edge : mst) {
        cout << edge.src << " - " << edge.dest << "\t" << edge.weight << endl;
    }
}

int main() {
    int V = 5; // 顶点数
    // 邻接矩阵，表示图的连接关系和权重，INT_MAX表示无边
    int graph[5][5] = {
        {0, 10, 6, INT_MAX, INT_MAX},
        {10, 0, INT_MAX, 15, INT_MAX},
        {6, INT_MAX, 0, 4, INT_MAX},
        {INT_MAX, 15, 4, 0, INT_MAX},
        {INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0}
    };

    cout << "Prim" << endl;
    vector<Edge> mstPrim = primMST(V, graph); // 使用普里姆算法找到MST
    printMST(mstPrim); // 打印MST

    cout << "\nKruskal" << endl;
    vector<Edge> mstKruskal = kruskalMST(V, graph); // 使用克鲁斯卡尔算法找到MST
    printMST(mstKruskal); // 打印MST

    return 0; // 程序结束
}